package com.kobeliu.entity;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Demo_17_No15_2 {
    public static void main(String[] args) {

    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0) break; //因为是排过序的，所以i位置大于零，后面的位置也都大于0
            if(i>0 && nums[i]==nums[i-1]) continue; //去重

            int j = i+1; //左边的指针
            int k = len-1; //右边的指针

            while(j<k){
                int sum = nums[i]+nums[j]+nums[k];
                if(sum==0){
                    lists.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    //这两句需要理解,去重
                    while(j<k && nums[j]== nums[j+1]) j++;
                    while(j<k && nums[k]== nums[k-1]) k--;
                    j++;
                    k--;
                }else if(sum<0){
                    j++;
                }else{
                    k--;
                }
            }
        }
        return lists;
    }
//     private static void Mergesort(int[] nums, int low, int high) {
//         if(low < high){
// //            int mid = (high + low)/2;
//             int mid = low + ((high - low)>>1); //>>的优先即
//             Mergesort(nums,low,mid);
//             Mergesort(nums,mid+1,high);
//             merge(nums,low,mid,high);
//         }
//     }
//     private static void merge(int[] nums, int low, int mid, int high) {
//         int[] help = new int[high-low+1];
//         int p = low; //左数组指针
//         int q = mid+1; //右数组指针
//         int i = 0; //help数组指针
//         while(p<=mid && q<=high){
//             help[i++] = nums[p] < nums[q] ? nums[p++]:nums[q++];
//         }
//         while(p<=mid){
//             help[i++] = nums[p++];
//         }
//         while(q<=high){
//             help[i++] = nums[q++];
//         }
//         for (int j = 0; j < i; j++) {
//             nums[low+j] = help[j];
//         }
//     }
}
